package algorithms.leaning.class12;

import common.bean.TreeNode;

/**
 * 判断二叉树是不是平衡二叉树
 * 每个节点的左右子树高度差不可超过1
 *
 * @author guichang
 * @date 2021/6/12
 */

@SuppressWarnings("all")
public class Code2_二叉树_平衡二叉树 {
    // 1、左树是否平衡，右树是否平衡
    // 2、左树高度，右树高度
    public static boolean isBalance(TreeNode node) {
        return process(node).balance;
    }

    private static Info process(TreeNode node) {
        if (node == null) {
            return new Info(true, 0);
        }
        Info tl = process(node.left);
        Info tr = process(node.right);
        boolean balance = tl.balance && tr.balance && (Math.abs(tl.height - tr.height) <= 1);
        int height = Math.max(tl.height, tr.height) + 1;
        return new Info(balance, height);
    }

    private static class Info {
        boolean balance; // 是否平衡
        int height; // 树高度

        public Info(boolean balance, int height) {
            this.balance = balance;
            this.height = height;
        }
    }

}